package Bit;
import  java.util.*;
/**
 * 基于整型的
 * 普通的二分搜索树
 * @author yuisama
 * @date 2022/03/11 21:09
 **/

public class SeachTree {
    private class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private int size;
    private TreeNode root;

    public void add(int val) {
        root = add(root, val);
    }

    private TreeNode add(TreeNode root, int val) {
        if (root == null) //如果树为空，创建新节点
        {
            TreeNode newNode = new TreeNode(val);
            size++; //空间+1
            return newNode;
        }
        if (val < root.val) {
            root.left = add(root.left, val);//递归左树查找，最后添加位叶子节点
        }
        if (val > root.val) {
            root.right = add(root.right, val);
        }
        return root;
    }

    public boolean cotians(int val) {
        return cotians(root, val);
    }

    private boolean cotians(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (val == root.val) {
            return true;
        }
        if (val > root.val) {
            return cotians(root.right, val);
        }
        if (val < root.val) {
            return cotians(root.left, val);
        }
    }

    public int findMin() {
        if(root==null)
        {
            throw new NoSuchElementException("BST is empty! cannot find min");
        }
        TreeNode minNode=minNode(root);
        return minNode.val;

    }

    private TreeNode minNode(TreeNode root) {
        if(root.left==null)  //左子树为空的节点，即为值最小的节点
        {
            return root;
        }
        return minNode(root.left);

    }
    public int findMax()
    {
        if(root==null)
        {
            throw new NoSuchElementException("BST is empty! cannot find min");
        }
        TreeNode maxNode=maxNode(root);
        return  maxNode.val;
    }

    private TreeNode maxNode(TreeNode root) {
        if(root.right==null)
        {
            return root;
        }
        return maxNode(root.right);

    }
    public int removeMax()
    {
        int max=findMax();
        root=removeMax(root);
        return max;
    }
    public  TreeNode removeMax(TreeNode root)
    {
        if(root.right==null) {
            TreeNode left = root.left;

            root.left = root = null;
            size--;
            return left;
        }
        root.right=removeMax(root.right);
        return  root;
    }
    public int removeMin()
    {
        int min=findMin();
        root=removeMin(root);
        return  min;
    }

    private TreeNode removeMin(TreeNode root) {
        if(root.left==null)
        {
            TreeNode right=root.right;
            size--;
            root.right=root=null;
            return right;
        }
        root.left=removeMin(root.left);
        return  root;
    }
    public void remove(int val)
    {
        root=remove(root,val);
    }

    private TreeNode remove(TreeNode root, int val) {
        if(root==null)
        {
            throw new NoSuchElementException("BST 中没有值为"+val+"的节点!");
        }
        else if(val<root.val)
        {
            root.left=remove(root.left,val)
                    return root;
        }
        else if(val>root.val)
        {
            root.right=remove(root.right,val);
            return  root;
        }
        else
        {
          if(root.left==null)
          {
              TreeNode right=root.right;
              root.right=root=null;
              size--;
              return right;
          }
          if(root.right==null)
          {
              TreeNode left=root.left;
              root.left=root=null;
              size--;
              return left;
          }
          TreeNode successor=minNode(root.right);
          successor.right=removeMin(root.right);
          successor.left=root.left;
          root.left=root.right=root=null;
          return  successor;
        }

    }


}
